#include<iostream>
#include<vector>
using namespace std;


class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        vector<int> rem(len + 10, INT_MAX);
        rem[0] = 0;
        for (int i = 0; i < len; i++) {
            if (rem[i] != INT_MAX)
                for (int j = 1; j <= nums[i] && i + j <= len; j++) {
                    rem[i + j] = min(rem[i + j], rem[i] + 1);
                }
        }
        return rem[len - 1];
    }
};

class Solution2 {
public:
    int jump(vector<int>& nums) {
        int maxPos = 0, n = nums.size(), end = 0, step = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (maxPos >= i) {
                maxPos = max(maxPos, i + nums[i]);
                if (i == end) {
                    end = maxPos;
                    ++step;
                }
            }
        }
        return step;
    }
};
